package com.LeeCode;

/**
 * 二叉树着色游戏
 */

public class Code1145 {
    public static void main(String[] args) {
        Integer[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code1145().btreeGameWinningMove(root, 11, 3));
    }

    private int leftNum, rightNum;

    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        dfs(root, x);
        if (leftNum >= (n + 1) / 2 || rightNum >= (n + 1) / 2 || (leftNum + rightNum + 1) <= n / 2) {
            return true;
        }
        return false;
    }


    private int dfs(TreeNode root, int key) {
        if (root == null) return 0;
        int left = dfs(root.left, key);
        int right = dfs(root.right, key);
        if (root.val == key) {
            this.leftNum = left;
            this.rightNum = right;
        }
        return left + right + 1;
    }
}
